/**
 * @file prim.c
 * @brief An implementation of Prim's minimum spanning tree algorithm
 * @author Matt Stallmann
 * @date June 25 1990
 * $Id: prim.c 11 2007-06-28 20:13:46Z mfms $
 */

/*
 *  Copyright (C) 1990, 2001  Matthias Stallmann.
 *  Contact: matt_stallmann@ncsu.edu
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License along
 *  with this program (file COPYING.txt); if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301
 *  USA.
 */

#include<stdio.h>
#include<limits.h>
#include "Gdr.h"

edge candidate[MAX_VERTEX];   /* candidate edge for this vertex */
int cost[MAX_VERTEX];      /* cost of the candidate edge */
int status[MAX_VERTEX];    /* status of this vertex -- use defines below */
#define in_tree 0
#define unseen 1
#define fringe 2

/* declarations and macros for the animation */
#define MSG_SIZE 100            /* maximum length of a message */
char msg[MSG_SIZE];
TWIN pwin;                      /* window for user prompts */
#define XW 1                    /* prompt window coordinates */
#define YW 1
#define init_prompt_window (pwin = create_text_window(XW,YW,""))
#define destroy_prompt_window (kill_window(pwin))
#define wait(msg) (write_text_window(pwin,msg),suspend_animation(),\
               hide_window(pwin))
#define COUNT 4

typedef struct cell {
  struct cell *next;
  vertex vx;
} *V_LIST;
V_LIST fringe_list = NULL;

void add_to_fringe_list(vertex v)
{
  V_LIST new_item;
  
  new_item = (V_LIST)calloc(1,sizeof(struct cell));
  new_item->next = fringe_list;
  new_item->vx = v;
  fringe_list = new_item;
}

void remove_from_fringe_list(V_LIST prev)
     /* pointer to cell before the one being removed;
                  NULL if first cell is to be removed */
{
  V_LIST out = (prev == NULL) ? fringe_list : prev->next;
  if (prev == NULL) 
    fringe_list = fringe_list->next;
  else
    prev->next = out->next;
  free(out);
}

int weight(edge e)   /* returns value of integer label */
           
{
  int wt;
  sscanf(edge_label(e),"%d",&wt);
  return (wt);
}

char *new_string(int i) /* returns a string representation of integer i */
          
{
  char *stg;
  stg = (char *)calloc(10,sizeof(char));
  sprintf(stg,"%d",i);
  return (stg);
}

void animat(void)
{
  vertex x;    /* current vertex */
  V_LIST x_pos;      /* x's position in the fringe list */
  int edge_count = 0;   /* number of edges in tree */
  vertex y;    /* generic vertex for loops */
  edge e;         /* generic edge */
  int maxv = max_vertex() + 1;  /* number of possible vertices */
  int n = 0;         /* number of valid vertices */
  int c;       /* a cost */
  int min_cost;      /* minimum cost in current iteration */
  int total_cost;    /* total cost of MST */
  V_LIST prev,ptr;   /* generic pointers to fringe list */
  
  init_prompt_window;
  wait("Starting with vertex 0\nClick Resume? to begin");
  
  /* hide labels on all edges */
  for (e = first_edge(); e != NULL_EDGE; e = next_edge(e)) {
    hide_edge_label(e);
  }
  
  /* initialize status and count number of valid vertices */
  for (y = 0; y < maxv; y++) {
    if (is_valid_vertex(y)) n++;
    status[y] = unseen;
  }
  
  
  total_cost = 0;
  x = get_a_vertex();
  status[x] = in_tree;
  highlight_vertex(x);
  
  while (edge_count < n-1) {
    /* traverse adjacency list for x */
    for (e = first_out_edge(x); e != NULL_EDGE;
         e = next_out_edge(x,e)) {
      y = other_vertex(x,e);
      if (status[y] == fringe) {
        highlight_edge(e);
        expose_edge_label(e);
        if ((c = weight(e)) < cost[y]) {
          /* y has a new candidate edge */
          change_vertex_label(y,new_string(c));
          candidate[y] = e;
          cost[y] = c;
        }
      }
      if (status[y] == unseen) {
        /* y is a new fringe vertex */
        c = weight(e);
        highlight_edge(e);
        expose_edge_label(e);
        change_vertex_label(y,new_string(c));
        expose_vertex_label(y);
      
        status[y] = fringe;
        add_to_fringe_list(y);
        candidate[y] = e;
        cost[y] = c;
      }
    } /* end of adjacency list traversal */
   
    wait("Ready to choose next tree edge\nClick Resume to continue");
   
    /* choose next tree edge (find lowest cost fringe vertex) */
    if (fringe_list == NULL) {
      printf("Graph is not connected\n");
      return;
    }
   
    min_cost = INT_MAX;
    for (ptr = fringe_list, prev = NULL;
         ptr != NULL; prev = ptr, ptr = ptr->next) {
      if (cost[ptr->vx] < min_cost) {
        min_cost = cost[ptr->vx];
        x = ptr->vx;
        x_pos = prev;
      }
    }        /* x is lowest cost vertex on fringe list */
    total_cost = total_cost + min_cost;
    remove_from_fringe_list(x_pos);
    status[x] = in_tree;
    edge_count++;
   
    blink_edge(candidate[x],COUNT);
    un_highlight_edge(candidate[x]);
    hide_edge_label(candidate[x]);
    highlight_vertex(x);
    hide_vertex_label(x);
   
    /* remove redundant edges */
    for (e = first_out_edge(x); e != NULL_EDGE;
         e = next_out_edge(x,e)) {
      y = other_vertex(x,e);
      if (status[y] == in_tree && !are_edges_equal(candidate[x],e)) {
        /* edge xy is redundant */
        hide_edge(e);
      }
    }
  }   /* end of main loop */
  
  /* expose labels on all displayed (tree) edges and highlight them,
     while showing other edges */
  for (e = first_edge(); e != NULL_EDGE; e = next_edge(e)) {
    if (is_displayed_edge(e)) {
      expose_edge_label(e);
      highlight_edge(e);
    }
    else {
      hide_edge_label(e);
      un_highlight_edge(e);
      display_edge(e);
    }
  }
  
  /* display total cost of MST */
  sprintf(msg,"Total cost = %d\n Click RESUME ? to end animation",
          total_cost);
  wait(msg);
} /* animat ends */

/*  [Last modified: 2007 06 28 at 20:12:29 GMT] */
